﻿/*
题目: 不同的子序列

给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 109 + 7 取模。

https://leetcode.cn/problems/distinct-subsequences/description/
*/

#include <iostream>
#include <random>
#include <string>
#include <vector>
#include <list>
#include "TreeNode.hpp"
#include "ListNode.hpp"
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <functional>

using namespace std;

class Solution {
public:
#define MOD (int)(1e9 + 7)

    int numDistinct(string s, string t) {
        // s 中子序列中 t 出现的次数
        int slen = s.size();
        int tlen = t.size();
        vector<vector<int>> dp(slen + 1, vector<int>(tlen + 1, 0));

        for (int i = 0; i <= slen; i++) {
            dp[i][0] = 1;
        }

        for (int i = 1; i <= slen; i++) {
            for (int j = 1; j <= tlen; j++) {
                bool eq = s[i - 1] == t[j - 1];
                // 如果不相等，那么可以直接忽略 s[i - 1] 这个字符
                if (!eq) {
                    dp[i][j] = dp[i - 1][j];
                }
                // 如果相等
                // dp[i - 1][j] 可以选择 s[0:i - 1] 上次匹配成功的结果，也就是没有 s[i] 的影响
                // dp[i - 1][j - 1] 可以选择 s[0:i - 1] s[0:j - 1] 匹配成功，比如 ab ab => abc abc
                else {
                    dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1]) % MOD;
                }
            }
        }

        return dp[slen][tlen];
    }
};
